import javafx.util.Pair;

import java.util.*;

/**
 * @author hewei
 * @version 1.0
 * @description: 786. 第 K 个最小的素数分数
 * @date 2022/8/25 15:43
 */

public class KthSmallestPrimeFraction {

    public static void main(String[] args) {
        KthSmallestPrimeFraction kthSmallestPrimeFraction = new KthSmallestPrimeFraction();
        int[] nums = {1, 3, 7, 13, 23, 29, 43, 47, 89, 97, 107, 113, 139, 191, 193, 211, 271, 331, 347, 349, 389, 419, 443, 461, 463, 487, 491, 557, 571, 587, 593, 613, 647, 661, 673, 677, 683, 727, 743, 751, 757, 761, 769, 773, 827, 877, 881, 883, 941, 967, 997, 1031, 1039, 1061, 1117, 1193, 1213, 1231, 1249, 1283, 1303, 1307, 1321, 1423, 1427, 1439, 1451, 1453, 1471, 1481, 1483, 1531, 1553, 1559, 1571, 1597, 1609, 1613, 1621, 1663, 1697, 1699, 1709, 1753, 1777, 1783, 1787, 1861, 1877, 1913, 1979, 1987, 1993, 1997, 2083, 2113, 2129, 2141, 2143, 2179, 2213, 2221, 2287, 2339, 2357, 2383, 2389, 2393, 2423, 2459, 2551, 2579, 2633, 2687, 2707, 2719, 2767, 2791, 2801, 2939, 2953, 2969, 3011, 3019, 3037, 3061, 3067, 3119, 3121, 3137, 3163, 3169, 3187, 3191, 3209, 3229, 3253, 3259, 3271, 3307, 3319, 3343, 3359, 3373, 3433, 3449, 3467, 3511, 3517, 3529, 3547, 3571, 3617, 3631, 3637, 3659, 3719, 3739, 3767, 3797, 3821, 3847, 3853, 3881, 3889, 3943, 3947, 3989, 4003, 4057, 4093, 4099, 4111, 4127, 4129, 4219, 4229, 4241, 4273, 4289, 4337, 4339, 4363, 4391, 4457, 4463, 4481, 4483, 4493, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4649, 4657, 4663, 4679, 4729, 4733, 4759, 4783, 4789, 4861, 4889, 4903, 4967, 4969, 4973, 5009, 5011, 5039, 5059, 5087, 5119, 5153, 5167, 5171, 5227, 5273, 5347, 5393, 5407, 5413, 5419, 5441, 5519, 5557, 5569, 5639, 5641, 5659, 5711, 5717, 5741, 5743, 5783, 5801, 5903, 5923, 5987, 6067, 6079, 6089, 6101, 6113, 6151, 6199, 6263, 6287, 6301, 6361, 6379, 6421, 6427, 6451, 6491, 6553, 6563, 6569, 6637, 6653, 6661, 6701, 6733, 6737, 6761, 6823, 6829, 6841, 6917, 6959, 7013, 7027, 7057, 7103, 7177, 7247, 7283, 7297, 7307, 7333, 7349, 7393, 7459, 7477, 7499, 7529, 7559, 7573, 7591, 7607, 7639, 7643, 7649, 7673, 7681, 7741, 7753, 7757, 7789, 7793, 7817, 7829, 7841, 7901, 7933, 7949, 7963, 8059, 8081, 8087, 8093, 8167, 8191, 8243, 8263, 8287, 8329, 8353, 8369, 8387, 8443, 8447, 8467, 8527, 8597, 8609, 8663, 8681, 8699, 8719, 8737, 8779, 8783, 8803, 8819, 8821, 8837, 8933, 8951, 8963, 8971, 9001, 9133, 9151, 9161, 9281, 9293, 9371, 9377, 9397, 9403, 9437, 9439, 9461, 9463, 9533, 9587, 9619, 9661, 9677, 9743, 9781, 9883, 9901, 9967, 10069, 10099, 10133, 10139, 10141, 10177, 10223, 10253, 10321, 10337, 10429, 10459, 10513, 10631, 10657, 10687, 10729, 10789, 10799, 10831, 10847, 10859, 10867, 10909, 10939, 10979, 10993, 11047, 11059, 11119, 11251, 11353, 11467, 11483, 11497, 11519, 11549, 11579, 11633, 11689, 11699, 11789, 11801, 11827, 11833, 11839, 11897, 11927, 11959, 11971, 11981, 12007, 12011, 12037, 12041, 12071, 12113, 12119, 12143, 12149, 12157, 12163, 12241, 12263, 12277, 12343, 12391, 12473, 12517, 12527, 12541, 12547, 12569, 12613, 12653, 12739, 12743, 12757, 12821, 12823, 12853, 12889, 12959, 12983, 13001, 13003, 13033, 13037, 13043, 13049, 13127, 13147, 13171, 13183, 13229, 13259, 13291, 13309, 13367, 13411, 13457, 13463, 13487, 13523, 13537, 13567, 13619, 13649, 13669, 13711, 13723, 13757, 13781, 13841, 13901, 13903, 13967, 13999, 14029, 14033, 14057, 14071, 14087, 14173, 14177, 14207, 14249, 14251, 14281, 14323, 14327, 14401, 14447, 14479, 14537, 14543, 14549, 14551, 14621, 14627, 14639, 14657, 14669, 14713, 14717, 14741, 14759, 14779, 14797, 14867, 14887, 14897, 14947, 14969, 15053, 15083, 15101, 15137, 15193, 15199, 15259, 15287, 15307, 15329, 15383, 15401, 15443, 15451, 15497, 15541, 15569, 15601, 15629, 15643, 15683, 15727, 15731, 15749, 15773, 15797, 15823, 15923, 15959, 15971, 15991, 16001, 16007, 16033, 16057, 16073, 16127, 16139, 16187, 16273, 16339, 16417, 16447, 16451, 16453, 16481, 16487, 16493, 16519, 16573, 16631, 16633, 16651, 16661, 16691, 16693, 16763, 16787, 16921, 16937, 16943, 16963, 17033, 17047, 17159, 17191, 17231, 17239, 17257, 17327, 17341, 17351, 17383, 17389, 17449, 17471, 17509, 17551, 17569, 17579, 17599, 17623, 17681, 17747, 17783, 17789, 17851, 17903, 17911, 17939, 17977, 18041, 18061, 18119, 18181, 18253, 18289, 18311, 18371, 18413, 18427, 18457, 18517, 18523, 18541, 18587, 18637, 18679, 18701, 18719, 18757, 18787, 18797, 18859, 18869, 18913, 18947, 18959, 19001, 19037, 19079, 19081, 19139, 19157, 19273, 19301, 19319, 19333, 19373, 19381, 19441, 19501, 19507, 19531, 19543, 19583, 19597, 19603, 19609, 19661, 19681, 19697, 19709, 19727, 19759, 19801, 19813, 19889, 19913, 19927, 19949, 19963, 19973, 19993, 20021, 20047, 20071, 20129, 20147, 20231, 20249, 20261, 20287, 20327, 20347, 20369, 20477, 20521, 20663, 20693, 20707, 20747, 20773, 20887, 20899, 20929, 20939, 20959, 20963, 21013, 21059, 21067, 21107, 21149, 21157, 21163, 21179, 21247, 21277, 21317, 21391, 21397, 21401, 21407, 21433, 21503, 21529, 21557, 21559, 21589, 21601, 21647, 21661, 21683, 21701, 21713, 21727, 21787, 21937, 21943, 21961, 21991, 22013, 22027, 22039, 22079, 22129, 22153, 22157, 22159, 22171, 22271, 22283, 22433, 22441, 22469, 22481, 22483, 22511, 22613, 22619, 22637, 22639, 22651, 22669, 22721, 22741, 22777, 22811, 22859, 22861, 22907, 22921, 22937, 22993, 23059, 23081, 23159, 23173, 23197, 23201, 23203, 23311, 23321, 23357, 23369, 23417, 23473, 23497, 23537, 23539, 23677, 23689, 23719, 23747, 23801, 23827, 23833, 23857, 23879, 23893, 23911, 23917, 23957, 24023, 24029, 24043, 24061, 24083, 24091, 24103, 24107, 24121, 24133, 24223, 24247, 24281, 24329, 24337, 24359, 24371, 24379, 24419, 24443, 24469, 24481, 24547, 24593, 24611, 24631, 24659, 24677, 24691, 24709, 24809, 24841, 24877, 24907, 24917, 24919, 24943, 24971, 24989, 25013, 25031, 25037, 25117, 25163, 25183, 25189, 25243, 25253, 25261, 25309, 25423, 25453, 25457, 25469, 25523, 25541, 25561, 25609, 25633, 25657, 25667, 25679, 25693, 25703, 25741, 25793, 25847, 25873, 25913, 25939, 25969, 25981, 26021, 26029, 26041, 26119, 26141, 26177, 26249, 26251, 26263, 26293, 26297, 26321, 26339, 26371, 26387, 26393, 26417, 26497, 26513, 26539, 26573, 26627, 26681, 26693, 26699, 26701, 26711, 26729, 26759, 26801, 26849, 26863, 26951, 26981, 27011, 27031, 27061, 27107, 27109, 27127, 27239, 27241, 27259, 27277, 27361, 27407, 27437, 27457, 27529, 27539, 27541, 27673, 27733, 27743, 27763, 27767, 27773, 27791, 27827, 27851, 27883, 27943, 27983, 28051, 28069, 28099, 28151, 28183, 28219, 28229, 28279, 28309, 28403, 28439, 28493, 28499, 28517, 28559, 28579, 28607, 28621, 28631, 28643, 28649, 28669, 28697, 28703, 28729, 28753, 28759, 28793, 28843, 28859, 28867, 28871, 28879, 28949, 29033, 29059, 29077, 29123, 29129, 29137, 29179, 29191, 29201, 29243, 29303, 29339, 29383, 29389, 29401, 29411, 29437, 29443, 29473, 29501, 29537, 29569, 29611, 29753, 29761, 29833, 29837, 29863, 29873, 29917, 29927, 29947, 29983, 29989};
        System.out.println(Arrays.toString(kthSmallestPrimeFraction.kthSmallestPrimeFraction(nums, 249750)));
    }

    public int[] kthSmallestPrimeFraction1(int[] arr, int k) {
        TreeSet<Pair<Integer, Integer>> heap = new TreeSet<>((a, b) -> arr[a.getKey()] * arr[b.getValue()] - arr[a.getValue()] * arr[b.getKey()]);
        heap.add(new Pair<>(0, arr.length - 1));
        int[] ans = new int[2];
        while (--k > 0) {
            Pair<Integer, Integer> pair = heap.pollFirst();
            Integer key = pair.getKey();
            Integer value = pair.getValue();
            if (value - key > 1) {
                heap.add(new Pair<>(key, value - 1));
                heap.add(new Pair<>(key + 1, value));
            }
        }
        ans[0] = arr[heap.first().getKey()];
        ans[1] = arr[heap.first().getValue()];
        return ans;
    }

    public int[] kthSmallestPrimeFraction2(int[] arr, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> arr[a[0]] * arr[b[1]] - arr[a[1]] * arr[b[0]]);
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            heap.offer(new int[]{0, i});
        }
        while (--k > 0) {
            int[] poll = heap.poll();
            if (poll[0] + 1 <= poll[1]) {
                heap.offer(new int[]{poll[0] + 1, poll[1]});
            }
        }
        return new int[]{arr[heap.peek()[0]], arr[heap.peek()[1]]};
    }

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        double l = 0;
        double r = 1;
        while (true) {
            double mid = (r + l) / 2;
            int res = 0;
            int left = 0;
            int right = 1;
            int x = 0;
            int y = 1;
            while (right < arr.length) {
                while (left < right && (double) arr[left] / arr[right] < mid) {
                    if (x * arr[right] < arr[left] * y) {
                        x = arr[left];
                        y = arr[right];
                    }
                    ++left;
                }
                right++;
                res += left;
            }
            if (res > k) {
                r = mid;
            } else if (res < k) {
                l = mid;
            } else return new int[]{x, y};
        }
    }
}
